﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using UnityEngine;

namespace Assets.Scripts.LDS
{
    class SemGraphMatcher
    {
        SceneSemGraphManager m_sceneSemGraphManager;//generate
        RelationModelManager m_relModelManager;//generate
        SemanticGraph m_querySSG;//updateQuerySG

        public SemGraphMatcher(SceneSemGraphManager ssgManager, RelationModelManager relManager)
        {
            m_sceneSemGraphManager = ssgManager;
            m_relModelManager = relManager;

            TextDialog.textDebug("SemGraphMatcher: loading semantic graphs number " + m_sceneSemGraphManager.m_ssgNum);
        }


        public void updateQuerySG(SemanticGraph sg)
        {
            m_querySSG = sg;
        }

        /// <summary>
        /// get matched ssg over queryssg
        /// </summary>
        /// <param name="targetMatchNum"></param>
        /// <returns></returns>
        public List<SceneSemGraph> retrieveDatabaseSSGs(int targetMatchNum)
        {
            TextDialog.textDebug("SemGraphMatcher: start graph matching.");

            List<(double score, SceneSemGraph ssg)> scoredDBSubSSGs = new List<(double score, SceneSemGraph ssg)>();
            double exactMatchScore = m_querySSG.m_nodes.Count;
            int exactMatchNum = 0;
            List<SceneSemGraph> matchedSubSSGs = new List<SceneSemGraph>();


            // align to each dbSSG and compute align score
            for (int i = 0; i < m_sceneSemGraphManager.m_ssgNum; i++)
            {
                SceneSemGraph currDBSSG = m_sceneSemGraphManager.getGraph(i);

                double matchingScore = 0;
                SceneSemGraph subSSG = alignQuerySSGWithDBSSG(m_querySSG, currDBSSG, ref matchingScore);
                subSSG.m_dbSSGId = i;

                // for now we needn't the blacklist function
                //if (!ssgContainsBlackListModel(subSSG))
                //{
                scoredDBSubSSGs.Add((matchingScore, subSSG));
                if (matchingScore == exactMatchScore)
                {
                    exactMatchNum++;
                }
                //}
            }

            if (scoredDBSubSSGs.Count == 0)
            {
                TextDialog.textDebug("There is no matched DB SSG !!");
                return matchedSubSSGs;
            }



            // find top score subSSGs
            // descending order
            scoredDBSubSSGs.Sort((x, y) => x.score != y.score ? -x.score.CompareTo(y.score) : -x.ssg.m_dbSSGId.CompareTo(y.ssg.m_dbSSGId));

            int matchedSSGNum = scoredDBSubSSGs.Count;

            //List<int> videoIdList = new List<int>(3); //useless

            List<int> nonRepeatSSGIds = findNonRepeatSSGs(scoredDBSubSSGs, targetMatchNum);

            for (int i = 0; i < nonRepeatSSGIds.Count; i++)
            {
                int sgId = nonRepeatSSGIds[i];
                SceneSemGraph ssg = scoredDBSubSSGs[sgId].ssg;

                if (ssg != null)
                {
                    matchedSubSSGs.Add(ssg);
                }
            }

            // enrich subSSG
            for (int i = 0; i < matchedSubSSGs.Count; i++)
            {
                SceneSemGraph matchedSubSSG = matchedSubSSGs[i];
                SceneSemGraph dbSSG = m_sceneSemGraphManager.getGraph(matchedSubSSG.m_dbSSGId);

                // add the active objects for group relations since we have only added the group relation node to SSG
                addGroupActNodesToSubSSG(matchedSubSSG, dbSSG);

                // add the synthesized node specified by the query text

                if (Params.addSynthNode)
                {
                    addSynthNodeToSubSSG(matchedSubSSG, dbSSG);
                }
                matchedSubSSG.restoreMissingSupportRelationNodes();
                addInferredSuppParentNodesToSubSSG(matchedSubSSG, dbSSG);

            }



            // Following settings are to create more types of results for comparison
            // 1. when input is not adding synth nodes, but addSynthSceneNum is larger than 0, will add scenes with synth node to compare with or without synth nodes
            List<SceneSemGraph> addedSubSSGs = new List<SceneSemGraph>();
            if (!Params.addSynthNode)
            {
                for (int a = 0; a < Params.addSynthSceneNum; a++)
                {
                    SceneSemGraph subSSGWithSynNode = new SceneSemGraph(matchedSubSSGs[a]);
                    SceneSemGraph dbSSG = m_sceneSemGraphManager.getGraph(matchedSubSSGs[a].m_dbSSGId);
                    addSynthNodeToSubSSG(subSSGWithSynNode, dbSSG);
                    subSSGWithSynNode.restoreMissingSupportRelationNodes();
                    addedSubSSGs.Add(subSSGWithSynNode);
                }
            }

            // 2. add extra scenes with context; add context to first specifed number of scenes in current result list
            int addedSSGNum = addedSubSSGs.Count;
            if (Params.isUseContext)
            {
                if (Params.showBothOriginAndContextView)
                {
                    // add context to new views
                    for (int a = 0; a < Params.addContextSceneNum; a++)
                    {
                        // if no extra scenes with syn node added, add context nodes to original matched ssgs
                        if (addedSSGNum == 0)
                        {
                            SceneSemGraph subSSGWithContext = new SceneSemGraph(matchedSubSSGs[a]);
                            SceneSemGraph dbSSG = m_sceneSemGraphManager.getGraph(matchedSubSSGs[a].m_dbSSGId);
                            addContextNodesFromDbSSGToSubSSG(subSSGWithContext, dbSSG);
                            addedSubSSGs.Add(subSSGWithContext);
                        }
                        else if (a < addedSSGNum)
                        {
                            // add context nodes to ssgs with synth nodes
                            SceneSemGraph subSSGWithContext = new SceneSemGraph(addedSubSSGs[a]);
                            SceneSemGraph dbSSG = m_sceneSemGraphManager.getGraph(addedSubSSGs[a].m_dbSSGId);
                            addContextNodesFromDbSSGToSubSSG(subSSGWithContext, dbSSG);
                            addedSubSSGs.Add(subSSGWithContext);
                        }
                    }
                }
                // directly add context to the original views
                // will be the default setting for producing most results with context 
                else
                {
                    for (int a = 0; a < matchedSubSSGs.Count; a++)
                    {
                        SceneSemGraph dbSSG = m_sceneSemGraphManager.getGraph(matchedSubSSGs[a].m_dbSSGId);
                        addContextNodesFromDbSSGToSubSSG(matchedSubSSGs[a], dbSSG);
                    }
                }
            }

            for (int a = 0; a < addedSubSSGs.Count; a++)
            {
                matchedSubSSGs.Add(addedSubSSGs[a]);
            }

            TextDialog.textDebug("SemGraphMatcher: graph matching done, found instance num " + matchedSSGNum +
                ", exact match num " + exactMatchNum
                + ", shown instance num " + matchedSubSSGs.Count + ".\n");
            return matchedSubSSGs;

        }

        /// <summary>
        /// compute score of queryssg on dbssg, and generate a subssg
        /// </summary>
        /// <param name="querySSG"></param>
        /// <param name="dbSSG"></param>
        /// <param name="matchingScore"></param>
        /// <returns></returns>
        public SceneSemGraph alignQuerySSGWithDBSSG(SemanticGraph querySSG, SceneSemGraph dbSSG, ref double matchingScore)
        {
            SceneSemGraph matchedSubSSG = new SceneSemGraph();

            // Clear aligned info
            querySSG.m_nodeAlignMap.Clear();
            querySSG.setNodesUnAligned();
            dbSSG.setNodesUnAligned();

            // Clear saved query 
            if (dbSSG.m_alignedQuerySSG != null)
            {
                dbSSG.m_alignedQuerySSG = new SemanticGraph();
            }

            // align object and relation node, each node 10 points
            querySSG.alignObjectNodesToGraph(dbSSG, ref matchingScore);
            querySSG.alignRelationNodesToGraph(dbSSG, ref matchingScore);

            // collect matched nodes and generate subgraph
            List<int> matchedDBSsgNodeList = new List<int>();
            for (int ni = 0; ni < querySSG.m_nodeNum; ni++)
            {
                SemNode sgNode = querySSG.m_nodes[ni];

                if (sgNode.isAligned && querySSG.m_nodeAlignMap.ContainsKey(ni))
                {
                    int matchedDBSsgNodeId = querySSG.m_nodeAlignMap[ni];

                    // adjust matching score for special objects
                    //if (sgNode.nodeType == "object")
                    //{
                    //MetaModel dbMd = dbSSG.getModelWithNodeId(matchedDBSsgNodeId);
                    //  track......
                    //if (dbMd.catName == "book" && Vector3.Dot(dbMd.frontDir, new Vector3(0, 0, 1)) < 0.5)
                    //{
                    //    matchingScore -= 20;
                    //}
                    //}

                    matchedDBSsgNodeList.Add(matchedDBSsgNodeId);
                }
            }

            // add nodes by exact match and scene context
            matchedSubSSG = dbSSG.getSubGraph(matchedDBSsgNodeList);
            dbSSG.m_alignedQuerySSG = new SemanticGraph(querySSG); // save a copy of aligned query SSG in correspond dbSSG

            return matchedSubSSG;
        }


        public void addEdgesToSubSSG(SceneSemGraph matchedSubSSG, SceneSemGraph dbSSG)
        {
            // build graph edges
            for (int i = 0; i < dbSSG.m_edgeNum; i++)
            {
                SemEdge dbEdge = dbSSG.m_edges[i];

                if (dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbEdge.sourceNodeId)
                    && dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbEdge.targetNodeId))
                {
                    int newSourceId = dbSSG.m_dbNodeToSubNodeMap[dbEdge.sourceNodeId];
                    int newTargetId = dbSSG.m_dbNodeToSubNodeMap[dbEdge.targetNodeId];

                    if (!matchedSubSSG.isEdgeExist(newSourceId, newTargetId))
                    {
                        matchedSubSSG.addEdge(newSourceId, newTargetId);
                    }
                }
            }
        }
        public void addGroupActNodesToSubSSG(SceneSemGraph matchedSubSSG, SceneSemGraph dbSSG)
        {
            if (m_relModelManager.m_groupRelModels.Count == 0)
            {
                TextDialog.textDebug("No group relation models loaded from DB\n");
                return;
            }

            int initNodeNum = matchedSubSSG.m_nodeNum;
            int currSubSSGNodeNum = initNodeNum;

            List<int> insertDbObjNodeList = new List<int>();

            // add active obj node for group node in subSSG
            for (int i = 0; i < initNodeNum; i++)
            {
                SemNode sgNode = matchedSubSSG.m_nodes[i];
                if (sgNode.nodeType == "group_relation")
                {
                    int dbNodeId = Util.getKeyForValueInMap(dbSSG.m_dbNodeToSubNodeMap, i);
                    if (dbNodeId != -1)
                    {
                        SemNode dbNode = dbSSG.m_nodes[dbNodeId];


                        if (dbNode.anchorNodeList.Count != 0 && dbNode.matchingStatus == (int)SemNode.NodeMatchingStatus.ExplicitNode)
                        {
                            int anchorObjId = dbNode.anchorNodeList[0];
                            SemNode anchorNode = dbSSG.m_nodes[anchorObjId];

                            List<int> actNodeList = new List<int>(dbNode.activeNodeList);
                            // insert act nodes based on occ prob and add support nodes
                            List<int> insertedObjNodeIds = new List<int>();
                            for (int a = 0; a < actNodeList.Count; a++)
                            {
                                int dbActNodeId = actNodeList[a];
                                // skip if node is already inserted
                                if (dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbActNodeId)) continue;

                                SemNode dbActNode = dbSSG.m_nodes[dbActNodeId];

                                //if (dbActNode.nodeName == "chair") continue;
                                //if (dbActNode.nodeName == "desk") continue;
                                //if (dbActNode.nodeName == "table") continue;

                                //String occKey = String.Format("{0}_{1}", dbActNode.nodeName, 1);  // Temp, extend to multiple instances later

                                dbActNode.isAnnotated = true;
                                dbActNode.isAligned = false;
                                matchedSubSSG.addNode(dbActNode);
                                dbSSG.m_dbNodeToSubNodeMap[dbActNodeId] = currSubSSGNodeNum;
                                insertDbObjNodeList.Add(dbActNodeId);
                                currSubSSGNodeNum++;

                                // add support node for current active object
                                addSupportParentNodesForGroupActNode(dbActNodeId, dbSSG, matchedSubSSG, ref currSubSSGNodeNum, insertDbObjNodeList);

                            }


                            /*
                            String groupKey = dbNode.nodeName + "_" + anchorNode.nodeName;

                            GroupRelationModel groupModel;
                            if (m_relModelManager.m_groupRelModels.ContainsKey(groupKey))
                            {
                                groupModel = m_relModelManager.m_groupRelModels[groupKey];
                            }
                            else
                            {
                                TextDialog.textDebug(String.Format("Group model %1 not exist", groupKey));
                                return;
                            }

                            List<int> actNodeList = new List<int>(dbNode.activeNodeList);

                            // insert act nodes based on occ prob and add support nodes
                            List<int> insertedObjNodeIds = new List<int>();
                            for (int a = 0; a < actNodeList.Count; a++)
                            {
                                int dbActNodeId = actNodeList[a];
                                // skip if node is already inserted
                                if (dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbActNodeId)) continue;

                                SemNode dbActNode = dbSSG.m_nodes[dbActNodeId];

                                //if (dbActNode.nodeName == "chair") continue;
                                //if (dbActNode.nodeName == "desk") continue;
                                //if (dbActNode.nodeName == "table") continue;

                                String occKey = String.Format("{0}_{1}", dbActNode.nodeName, 1);  // Temp, extend to multiple instances later

                                if (groupModel.m_occurModels.ContainsKey(occKey))
                                {
                                    double groupOccTh = Params.groupOccProb * 0.3; // reduce the threshold to bring in more active objects
                                    double randProb = Util.GenRandomDouble(0, groupModel.m_maxOccProb * groupOccTh);
                                    double probTh = groupModel.m_occurModels[occKey].m_occurProb;

                                    if (probTh > randProb)
                                    {
                                        dbActNode.isAnnotated = true;
                                        dbActNode.isAligned = false;
                                        matchedSubSSG.addNode(dbActNode);
                                        dbSSG.m_dbNodeToSubNodeMap[dbActNodeId] = currSubSSGNodeNum;
                                        insertDbObjNodeList.Add(dbActNodeId);
                                        currSubSSGNodeNum++;

                                        // add support node for current active object
                                        addSupportParentNodesForGroupActNode(dbActNodeId, dbSSG, matchedSubSSG, ref currSubSSGNodeNum, insertDbObjNodeList);
                                    }
                                }
                            }*/
                        }
                    }
                }
            }

            // add edges
            addEdgesToSubSSG(matchedSubSSG, dbSSG);

            // add active objs to meta scene
            int modelInSceneId = matchedSubSSG.m_graphNodeToModelListIdMap.Count;
            for (int i = 0; i < insertDbObjNodeList.Count; i++)
            {
                int dbActNodeId = insertDbObjNodeList[i];

                // non-object node is not saved in the map
                if (dbSSG.m_graphNodeToModelListIdMap.ContainsKey(dbActNodeId))
                {
                    int dbMetaModelId = dbSSG.m_graphNodeToModelListIdMap[dbActNodeId];

                    if (dbMetaModelId < dbSSG.m_modelNum)
                    {
                        dbSSG.m_graphMetaScene.m_metaModellList[dbMetaModelId].isSelected = Convert.ToInt32(dbSSG.m_nodes[dbActNodeId].isAnnotated);
                        matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(dbSSG.m_graphMetaScene.m_metaModellList[dbMetaModelId]);
                        int currNodeId = dbSSG.m_dbNodeToSubNodeMap[dbActNodeId];
                        matchedSubSSG.m_graphNodeToModelListIdMap[currNodeId] = modelInSceneId;
                        modelInSceneId++;
                    }
                }
            }

            matchedSubSSG.parseNodeNeighbors();
        }
        public void addSynthNodeToSubSSG(SceneSemGraph matchedSubSSG, SceneSemGraph dbSSG)
        {
            Dictionary<int, int> dbNodeToSubNodeMap = dbSSG.m_dbNodeToSubNodeMap;
            SemanticGraph querySSG = dbSSG.m_alignedQuerySSG;
            Dictionary<int, int> queryToSubSsgNodeMap = new Dictionary<int, int>();

            //collect matched nodes into the map
            for (int ni = 0; ni < querySSG.m_nodeNum; ni++)
            {
                SemNode sgNode = querySSG.m_nodes[ni];

                if (sgNode.isAligned && querySSG.m_nodeAlignMap.ContainsKey(ni))
                {
                    // first find the DB-SSG node corresponding to the query node
                    int dbNodeId = querySSG.m_nodeAlignMap[ni];
                    int subNodeId = dbNodeToSubNodeMap[dbNodeId];

                    // then find the Sub-SSG node for the query node
                    queryToSubSsgNodeMap[ni] = subNodeId;
                }
            }

            // insert synthesized object node
            for (int ni = 0; ni < querySSG.m_nodeNum; ni++)
            {
                SemNode sgNode = querySSG.m_nodes[ni];

                if (!sgNode.isAligned && !querySSG.m_nodeAlignMap.ContainsKey(ni))
                {
                    if (sgNode.nodeType == "object")
                    {
                        matchedSubSSG.addNode(sgNode);
                        int currNodeId = matchedSubSSG.m_nodeNum - 1;
                        matchedSubSSG.m_nodes[currNodeId].isSynthesized = true;
                        queryToSubSsgNodeMap[ni] = currNodeId;

                        // set meta data
                        List<int> instanceIds = new List<int>();
                        foreach (int i in matchedSubSSG.findExistingInstanceIds(sgNode.nodeName))
                        {
                            instanceIds.Add(i);
                        }

                        if (instanceIds.Count != 0)
                        {
                            MetaModel newMd = matchedSubSSG.m_graphMetaScene.m_metaModellList[instanceIds[0]];
                            matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(newMd);
                            matchedSubSSG.m_graphNodeToModelListIdMap[currNodeId] = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count - 1;
                        }
                        else
                        {
                            List<string> attriNames = new List<string>(querySSG.getAttriNamesForNode(ni));
                            MetaModel newMd = m_sceneSemGraphManager.retrieveForModelInstance(sgNode.nodeName, attriNames);
                            if (newMd.name.Length != 0)
                            {
                                matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(newMd);
                                matchedSubSSG.m_graphNodeToModelListIdMap[currNodeId] = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count - 1;
                            }
                            else
                            {
                                //TextDialog.textDebug("Failure: can not find model " + sgNode.nodeName + " in database");
                            }
                        }
                    }
                }
            }

            // insert synthesized attribute and relation node
            for (int ni = 0; ni < querySSG.m_nodeNum; ni++)
            {
                SemNode sgNode = querySSG.m_nodes[ni];

                if (!sgNode.isAligned && sgNode.matchingStatus == (int)SemNode.NodeMatchingStatus.ExplicitNode
                    && (sgNode.nodeType == "attribute" || sgNode.nodeType == "group_relation"))
                {
                    if (sgNode.outEdgeNodeList.Count != 0)
                    {
                        int refNodeId = sgNode.outEdgeNodeList[0];

                        // only insert the relationship node for the object that is matched
                        if (queryToSubSsgNodeMap.ContainsKey(refNodeId))
                        {
                            int subSSGRefNodeId = queryToSubSsgNodeMap[refNodeId];

                            // insert node
                            matchedSubSSG.addNode(sgNode);
                            int currNodeId = matchedSubSSG.m_nodeNum - 1;
                            matchedSubSSG.m_nodes[currNodeId].isSynthesized = true;

                            matchedSubSSG.addEdge(currNodeId, subSSGRefNodeId);
                            queryToSubSsgNodeMap[ni] = currNodeId;

                            // add act objects for group relation
                            if (sgNode.nodeType == "group_relation")
                            {
                                int subSSGGroupNodeId = queryToSubSsgNodeMap[ni];
                                string subSSGRefNodeName = matchedSubSSG.m_nodes[subSSGRefNodeId].nodeName;
                                string groupKey = sgNode.nodeName + "_" + subSSGRefNodeName;
                                GroupRelationModel groupModel;

                                if (m_relModelManager.m_groupRelModels.ContainsKey(groupKey))
                                {
                                    groupModel = m_relModelManager.m_groupRelModels[groupKey];

                                    int insertedActObjNum = 0;


                                    foreach (var it in groupModel.m_occurModels)
                                    {
                                        if (insertedActObjNum >= 10) break; // currently only allow insert 10 objects for one synthesized group relation

                                        string actObjName = it.Value.m_objName;
                                        if (actObjName == "chair") continue;
                                        if (actObjName == "desk") continue;
                                        if (actObjName == "table") continue;

                                        string supportRelKey = subSSGRefNodeName + "_" + actObjName + "_parentchild_vertsupport";
                                        if (!m_relModelManager.m_pairwiseRelModels.ContainsKey(supportRelKey)) continue; // only insert object that has appeared on the ref object
                                        if (m_relModelManager.m_pairwiseRelModels[supportRelKey].m_numInstance < 5) continue;  // only insert objects with more than a few occurrences

                                        double groupOccTh = Params.groupOccProb; // use the loaded threshold for synthesized act objects
                                        double randProb = Util.GenRandomDouble(0, groupModel.m_maxOccProb * groupOccTh);
                                        double probTh = it.Value.m_occurProb;

                                        if (probTh > randProb)
                                        {
                                            MetaModel newMd = m_sceneSemGraphManager.retrieveForModelInstance(actObjName, new List<string>());
                                            if (newMd.name.Length != 0)
                                            {
                                                matchedSubSSG.addNode("object", actObjName);
                                                currNodeId = matchedSubSSG.m_nodeNum - 1;
                                                int subSSGActNodeId = currNodeId;
                                                matchedSubSSG.m_nodes[currNodeId].isSynthesized = true;

                                                matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(newMd);
                                                matchedSubSSG.m_graphNodeToModelListIdMap[currNodeId] = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count - 1;

                                                matchedSubSSG.addEdge(currNodeId, subSSGGroupNodeId);

                                                // add support node and edge
                                                matchedSubSSG.addNode("pair_relation", "support");
                                                currNodeId = matchedSubSSG.m_nodeNum - 1;
                                                matchedSubSSG.m_nodes[currNodeId].isSynthesized = true;

                                                matchedSubSSG.addEdge(currNodeId, subSSGRefNodeId);
                                                matchedSubSSG.addEdge(subSSGActNodeId, currNodeId);
                                                insertedActObjNum++;
                                            }
                                            else
                                            {
                                                TextDialog.textDebug("Failure: can not find model " + sgNode.nodeName + " in database");
                                            }
                                        }
                                    }
                                }
                                else
                                {
                                    //TextDialog.textDebug("Group model " + groupKey + " not exist");
                                }
                            }
                        }
                    }
                }

                if (!sgNode.isAligned && (sgNode.nodeType == "pair_relation"))
                {
                    if (sgNode.anchorNodeList.Count != 0)
                    {
                        int refNodeId = sgNode.anchorNodeList[0];
                        int actNodeId = sgNode.activeNodeList[0];

                        if (queryToSubSsgNodeMap.ContainsKey(refNodeId) && queryToSubSsgNodeMap.ContainsKey(actNodeId))
                        {
                            // insert node
                            matchedSubSSG.addNode(sgNode);
                            int currNodeId = matchedSubSSG.m_nodeNum - 1;
                            matchedSubSSG.m_nodes[currNodeId].isSynthesized = true;

                            matchedSubSSG.addEdge(currNodeId, queryToSubSsgNodeMap[refNodeId]);
                            matchedSubSSG.addEdge(queryToSubSsgNodeMap[actNodeId], currNodeId);

                            if (queryToSubSsgNodeMap[refNodeId] == queryToSubSsgNodeMap[actNodeId])
                            {
                                TextDialog.textDebug("");
                            }

                            queryToSubSsgNodeMap[ni] = currNodeId;
                        }
                    }
                }
            }

            matchedSubSSG.parseNodeNeighbors();
        }

        public void addInferredSuppParentNodesToSubSSG(SceneSemGraph matchedSubSSG, SceneSemGraph dbSSG)
        {
            List<int> insertedParentNodeIds = new List<int>();

            // add support parent
            for (int i = 0; i < matchedSubSSG.m_nodes.Count; i++)
            {
                SemNode mActNode = matchedSubSSG.m_nodes[i];

                if (mActNode.nodeType == "object")
                {
                    bool isInSpecialRelation = false;
                    for (int r = 0; r < mActNode.outEdgeNodeList.Count; r++)
                    {
                        int relId = mActNode.outEdgeNodeList[r];
                        SemNode relNode = matchedSubSSG.m_nodes[relId];
                        if (relNode.nodeType.Contains("group") || relNode.nodeName == "under")
                        {
                            isInSpecialRelation = true;
                        }
                    }

                    if (isInSpecialRelation) continue;

                    int dbActNodeId = Util.getKeyForValueInMap(dbSSG.m_dbNodeToSubNodeMap, i);
                    int dbActNodeParentNodeId = dbSSG.findParentNodeIdForNode(dbActNodeId);
                    int mActNodeParentNodeId = matchedSubSSG.findParentNodeIdForNode(i);

                    if (dbActNodeParentNodeId != -1 && dbActNodeParentNodeId != 0 && mActNodeParentNodeId == -1)
                    {
                        SemNode dbActNode = dbSSG.m_nodes[dbActNodeId];
                        MetaModel dbActNodeParentMd = dbSSG.getModelWithNodeId(dbActNodeParentNodeId);

                        for (int j = 0; j < dbActNode.outEdgeNodeList.Count; j++)
                        {
                            int dbRelNodeId = dbActNode.outEdgeNodeList[j];
                            SemNode dbRelNode = dbSSG.m_nodes[dbRelNodeId];
                            if (dbRelNode.nodeName.Contains("support"))
                            {
                                // add support node
                                matchedSubSSG.addNode(dbRelNode);
                                int currRelNodeId = matchedSubSSG.m_nodeNum - 1;
                                dbSSG.m_dbNodeToSubNodeMap[dbRelNodeId] = currRelNodeId;
                                matchedSubSSG.addEdge(i, currRelNodeId); // e.g., (tv, support)
                                matchedSubSSG.m_nodes[currRelNodeId].isAligned = true;
                                matchedSubSSG.m_nodes[currRelNodeId].isSynthesized = false;

                                List<int> parentNodeIds = new List<int>(matchedSubSSG.findNodeWithName(dbActNodeParentMd.catName));

                                // add parent node
                                int currAnchorNodeId;


                                if (insertedParentNodeIds.Find(s => s == dbActNodeParentNodeId) != 0)
                                {
                                    currAnchorNodeId = dbSSG.m_dbNodeToSubNodeMap[dbActNodeParentNodeId];
                                }
                                else if (parentNodeIds.Count != 0)
                                {
                                    currAnchorNodeId = parentNodeIds[0];
                                }
                                else
                                {
                                    matchedSubSSG.addNode(dbSSG.m_nodes[dbActNodeParentNodeId]);
                                    currAnchorNodeId = matchedSubSSG.m_nodeNum - 1;
                                    matchedSubSSG.m_nodes[currAnchorNodeId].inferedType = (int)SemNode.InferNodeType.InferBySupport;
                                    matchedSubSSG.m_nodes[currAnchorNodeId].isInferred = true;
                                    matchedSubSSG.m_nodes[currAnchorNodeId].inferRefNodeId = i;
                                    dbSSG.m_dbNodeToSubNodeMap[dbActNodeParentNodeId] = currAnchorNodeId;

                                    insertedParentNodeIds.Add(dbActNodeParentNodeId);

                                    // add meta model
                                    MetaModel newMd = dbSSG.getModelWithNodeId(dbActNodeParentNodeId);
                                    matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(newMd);
                                    matchedSubSSG.m_graphNodeToModelListIdMap[currAnchorNodeId] = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count - 1;
                                }

                                matchedSubSSG.addEdge(currRelNodeId, currAnchorNodeId); // e.g. (support, tv_stand)
                            }
                        }
                    }
                }
            }

            matchedSubSSG.parseNodeNeighbors();
        }

        public void addContextNodesFromDbSSGToSubSSG(SceneSemGraph matchedSubSSG, SceneSemGraph dbSSG)
        {
            int initSubSSGNodeNum = matchedSubSSG.m_nodes.Count;
            int currSubSSGNodeNum = initSubSSGNodeNum;
            int initSubSSGModelNum = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count;

            //std::vector<int> dbActNodeInsertedTimesForCurrAnchorNode(dbSSG->m_nodes.size(), 0);
            Dictionary<int, List<int>> dbActNodeInsertedTimesForCurrAnchorNode = new Dictionary<int, List<int>>();

            dbActNodeInsertedTimesForCurrAnchorNode[-1] = new List<int>();  // for room as anchor
            for (int i = 0; i < dbSSG.m_nodes.Count; i++)
            {
                dbActNodeInsertedTimesForCurrAnchorNode[-1].Add(0);
            }

            for (int i = 0; i < initSubSSGNodeNum; i++)
            {
                if (matchedSubSSG.isAnchor(i))
                {
                    dbActNodeInsertedTimesForCurrAnchorNode[i] = new List<int>();  // for room as anchor
                    for (int j = 0; j < dbSSG.m_nodes.Count; j++)
                    {
                        dbActNodeInsertedTimesForCurrAnchorNode[i].Add(0);
                    }
                }
            }

            for (int i = 0; i < initSubSSGNodeNum; i++)
            {
                SemNode mActNode = matchedSubSSG.m_nodes[i];
                string mActObjName = mActNode.nodeName;
                if (matchedSubSSG.m_nodes[i].nodeType == "object")
                {
                    int mParentNodeId = matchedSubSSG.findParentNodeIdForNode(i);
                    string mParentObjName;
                    if (mParentNodeId == -1)
                    {
                        mParentObjName = "room";
                    }
                    else
                    {
                        SemNode mParentNode = matchedSubSSG.m_nodes[mParentNodeId];
                        mParentObjName = matchedSubSSG.m_nodes[mParentNodeId].nodeName;
                    }

                    List<int> mParentIds = new List<int>();
                    foreach (int j in matchedSubSSG.findExistingInstanceIds(mParentObjName))
                    {
                        mParentIds.Add(matchedSubSSG.findExistingInstanceIds(mParentObjName)[j]);
                    }

                    for (int j = 0; j < dbSSG.m_nodes.Count; j++)
                    {
                        int dbActNodeId = j;

                        //// skip if node is already inserted; find if there is another anchor 
                        //if (dbSSG->m_dbNodeToSubNodeMap.count(dbActNodeId) && dbActNodeInsertedTimes[dbActNodeId] >= mParentIds.size())

                        SemNode dbActNode = dbSSG.m_nodes[dbActNodeId];
                        if (dbActNode.nodeType == "object")
                        {
                            string dbActObjName = dbActNode.nodeName;

                            if (dbActObjName == "desk" || dbActObjName == "table") continue; // do not insert table

                            if (matchedSubSSG.hasObj(dbActObjName, initSubSSGModelNum)) continue; // do not insert repeatably

                            MetaModel md = dbSSG.getModelWithNodeId(dbActNodeId);
                            if (m_sceneSemGraphManager.isModelInBlackList(md.name)) continue;  // do not insert black list model

                            int dbParentNodeId = dbSSG.findParentNodeIdForNode(dbActNodeId);

                            // one each dbsg node can only be added to one anchor
                            if (dbActNodeInsertedTimesForCurrAnchorNode.ContainsKey(mParentNodeId))
                            {
                                if (mParentNodeId != -1 && dbActNodeInsertedTimesForCurrAnchorNode[mParentNodeId][dbActNodeId] > 0)
                                {
                                    continue;
                                }
                            }

                            if (dbActObjName == "tableclock" && dbActNodeInsertedTimesForCurrAnchorNode[mParentNodeId][dbActNodeId] == 1) continue;

                            // parent node must be already inserted in sub-scene
                            if (!dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbParentNodeId) && dbParentNodeId != -1) continue;

                            string dbParentObjName = "";
                            if (dbParentNodeId != -1)
                            {
                                dbParentObjName = dbSSG.m_nodes[dbParentNodeId].nodeName;
                            }

                            if ((dbParentNodeId != -1 && mParentNodeId == dbSSG.m_dbNodeToSubNodeMap[dbParentNodeId])
                                || (mParentNodeId == dbParentNodeId && dbParentNodeId == -1) ||
                                dbParentObjName == mParentObjName)
                            {
                                double coOccProb = m_relModelManager.getCoOccProbOnParent(mActObjName, dbActObjName, mParentObjName);

                                if (coOccProb >= Params.contextCoOccProb)
                                {
                                    matchedSubSSG.addNode(dbActNode);
                                    int currActNodeId = matchedSubSSG.m_nodeNum - 1;
                                    matchedSubSSG.m_nodes[currActNodeId].inferedType = (int)SemNode.InferNodeType.InferByContext;
                                    matchedSubSSG.m_nodes[currActNodeId].isInferred = true;
                                    matchedSubSSG.m_nodes[currActNodeId].inferRefNodeId = i;
                                    dbSSG.m_dbNodeToSubNodeMap[dbActNodeId] = currActNodeId;

                                    // add meta model
                                    MetaModel newMd = dbSSG.getModelWithNodeId(dbActNodeId);
                                    matchedSubSSG.m_graphMetaScene.m_metaModellList.Add(newMd);
                                    matchedSubSSG.m_graphNodeToModelListIdMap[currActNodeId] = matchedSubSSG.m_graphMetaScene.m_metaModellList.Count - 1;

                                    dbActNodeInsertedTimesForCurrAnchorNode[mParentNodeId][dbActNodeId]++;
                                    matchedSubSSG.m_addedContextNodeIds.Add(currActNodeId);

                                    // add support node and edges
                                    for (int r = 0; r < dbActNode.outEdgeNodeList.Count; r++)
                                    {
                                        int dbRelNodeId = dbActNode.outEdgeNodeList[r];
                                        SemNode dbRelNode = dbSSG.m_nodes[dbRelNodeId];
                                        bool isFindParent = false;

                                        if (dbRelNode.nodeName.Contains("support"))
                                        {
                                            for (int k = 0; k < dbRelNode.outEdgeNodeList.Count; k++)
                                            {
                                                int anchorNodeId = dbRelNode.outEdgeNodeList[k];
                                                if (anchorNodeId == dbParentNodeId)
                                                {
                                                    isFindParent = true;
                                                    break;
                                                }
                                            }

                                            if (isFindParent)
                                            {
                                                // add support node
                                                matchedSubSSG.addNode(dbRelNode);
                                                int currRelNodeId = matchedSubSSG.m_nodeNum - 1;
                                                matchedSubSSG.addEdge(currActNodeId, currRelNodeId); // e.g., (tv, support)
                                                matchedSubSSG.addEdge(currRelNodeId, mParentNodeId); // e.g., (tv, support)


                                                matchedSubSSG.m_nodes[currRelNodeId].isAligned = true;
                                                matchedSubSSG.m_nodes[currRelNodeId].isSynthesized = false;
                                                dbSSG.m_dbNodeToSubNodeMap[dbRelNodeId] = currRelNodeId;

                                                break;
                                            }
                                        }
                                    }

                                    //special handling for chair
                                    if (mActObjName == "desk" && dbActObjName == "chair")
                                    {
                                        // add a near node
                                        matchedSubSSG.addNode(SemanticGraph.SSGNodeType[(int)SemNode.NodeType.Pair], "near");
                                        int currRelNodeId = matchedSubSSG.m_nodeNum - 1;
                                        matchedSubSSG.addEdge(currActNodeId, currRelNodeId); // e.g., (tv, support)
                                        matchedSubSSG.addEdge(currRelNodeId, i); // e.g., (tv, support)
                                    }
                                }
                            }
                        }
                    }
                }
            }

            matchedSubSSG.parseNodeNeighbors();
            matchedSubSSG.restoreMissingSupportRelationNodes();
        }

        //void addSupportParentNodesForGroupActNode(int dbActNodeId, SceneSemGraph* dbSSG, SceneSemGraph* matchedSubSSG, int &currSubSSGNodeNum, std::vector<int> &insertDbObjNodeList);
        public void addSupportParentNodesForGroupActNode(int dbActNodeId, SceneSemGraph dbSSG, SceneSemGraph matchedSubSSG, ref int currSubSSGNodeNum, List<int> insertDbObjNodeList)
        {
            bool reachBaseObj = false;
            SemNode currActNode = dbSSG.m_nodes[dbActNodeId];
            while (!reachBaseObj)
            {
                bool hasSuppNode = false;
                for (int r = 0; r < currActNode.outEdgeNodeList.Count; r++)
                {
                    int suppNodeId = currActNode.outEdgeNodeList[r];
                    SemNode suppNode = dbSSG.m_nodes[suppNodeId];
                    if (suppNode.nodeName.Contains("support") && suppNode.anchorNodeList.Count != 0)
                    {
                        // to insert a support node, it's anchor object must be already in the scene
                        int dbAnchorId = suppNode.anchorNodeList[0];
                        if (!dbSSG.m_dbNodeToSubNodeMap.ContainsKey(dbAnchorId))
                        {
                            SemNode dbAnchorNode = dbSSG.m_nodes[dbAnchorId];
                            //if (dbAnchorNode.nodeName == "room" || dbAnchorNode.nodeName == "chair" || dbAnchorNode.nodeName == "table")
                            //{
                            //    reachBaseObj = true;
                            //    break;
                            //}

                            dbAnchorNode.isAnnotated = true;
                            dbAnchorNode.isAligned = false;

                            // insert the support parent of a floating act object
                            matchedSubSSG.addNode(dbAnchorNode);
                            dbSSG.m_dbNodeToSubNodeMap[dbAnchorId] = currSubSSGNodeNum;

                            currSubSSGNodeNum++;
                            currActNode = dbAnchorNode;

                            insertDbObjNodeList.Add(dbAnchorId);
                        }
                        else
                        {
                            reachBaseObj = true;
                        }

                        suppNode.isAnnotated = true;
                        suppNode.isAligned = false;

                        matchedSubSSG.addNode(suppNode);
                        dbSSG.m_dbNodeToSubNodeMap[suppNodeId] = currSubSSGNodeNum;
                        currSubSSGNodeNum++;

                        hasSuppNode = true;
                    }
                }

                if (!hasSuppNode) reachBaseObj = true;
            }
        }


        //vector<int> findNonRepeatSSGs(const vector<pair<double, SceneSemGraph*>> &scoredDBSubSSGs, int targetNum);
        //bool ssgContainsBlackListModel(SceneSemGraph* ssg);
        //double computeGeometrySimilarity(SceneSemGraph* testSSG, SceneSemGraph* refSSG); // debug: simple compute similarity by matching node name
        public List<int> findNonRepeatSSGs(List<(double, SceneSemGraph)> scoredDBSubSSGs, int targetNum)
        {
            // some SSGs are same since the subscenes may be re-used in multiple scenes

            int matchedSSGNum = scoredDBSubSSGs.Count;
            targetNum = Math.Min(targetNum, matchedSSGNum);

            List<int> nonRepeatSSGids = new List<int>();
            nonRepeatSSGids.Add(0);

            for (int i = 1; i < matchedSSGNum; i++)
            {
                bool isRepeat = false;

                if (nonRepeatSSGids.Count == targetNum)
                {
                    break;
                }

                for (int ni = 0; ni < nonRepeatSSGids.Count; ni++)
                {
                    int refSSGId = nonRepeatSSGids[ni];
                    double simVal = computeGeometrySimilarity(scoredDBSubSSGs[i].Item2, scoredDBSubSSGs[refSSGId].Item2);

                    if (simVal > 0.8)
                    {
                        isRepeat = true;
                        break;
                    }
                }

                if (!isRepeat)
                {
                    nonRepeatSSGids.Add(i);
                }
            }

            return nonRepeatSSGids;
        }

        public bool ssgContainsBlackListModel(SceneSemGraph ssg)
        {
            for (int i = 0; i < ssg.m_graphMetaScene.m_metaModellList.Count; i++)
            {
                MetaModel md = ssg.m_graphMetaScene.m_metaModellList[i];
                if (m_sceneSemGraphManager.isModelInBlackList(md.name))
                {
                    return true;
                }
            }

            return false;
        }
        public double computeGeometrySimilarity(SceneSemGraph testSSG, SceneSemGraph refSSG)
        {
            double simVal = 0;
            double sceneMetric = Params.globalSceneUnitScale;
            double distTh = 0.1;

            List<int> refNodeIndicators = new List<int>();
            for (int i = 0; i < refSSG.m_nodeNum; i++)
            {
                refNodeIndicators.Add(0);
            }// indicator of whether a node is aligned

            for (int i = 0; i < testSSG.m_nodeNum; i++)
            {
                SemNode tsgNode = testSSG.m_nodes[i];

                if (tsgNode.nodeType == "object")
                {
                    MetaModel testModel = testSSG.getModelWithNodeId(i);

                    for (int j = 0; j < refSSG.m_nodeNum; j++)
                    {
                        SemNode rsgNode = refSSG.m_nodes[j];

                        if (!Convert.ToBoolean(refNodeIndicators[j]) && rsgNode.nodeType == "object" && tsgNode.nodeName == rsgNode.nodeName)
                        {
                            MetaModel refModel = refSSG.getModelWithNodeId(j);

                            // if hash name string is same
                            if (testModel.name == refModel.name)
                            {
                                Vector3 temp = (refModel.position - testModel.position);
                                double posDiff = Mathf.Sqrt(Vector3.Dot(temp, temp));

                                if (posDiff < distTh / sceneMetric)
                                {
                                    simVal += 1;
                                    refNodeIndicators[j] = 1;
                                }
                            }
                        }
                    }
                }
            }

            simVal = simVal / testSSG.m_graphMetaScene.m_metaModellList.Count;

            return simVal;
        }// debug: simple compute similarity by matching node name
    }
}
